﻿// 404 最小循环覆盖2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>

using  namespace std;


/*
http://oj.daimayuan.top/course/22/problem/935

给你一个字符串 a
，你需要求出这个字符串的字典序最小的最小循环覆盖。

b是 a 的最小循环覆盖，当且仅当 a是通过 b复制多次并连接后得到的字符串的子串，
且 b 是满足条件的字符串中长度最小的。你需要找出字典序最小的最小循环覆盖。

输入一个字符串 a，输出一个字符串表示字典序最小的最小循环覆盖。

输入格式
一行一个字符串 a。

输出格式
输出一行一个字符串表示答案。

样例输入1
bcabcabcabcab
样例输出1
abc
样例输入2
aaaaaaa
样例输出2
a
数据规模
对于所有数据，保证 1≤|a|≤105
，字符串均由小写字母构成。
*/


int nxt[200010];
char s[200010];

inline void getmin11(char s[]) {
	int n = strlen(s + 1);
	nxt[1] = 0;
	int j = 0;
	for (int i = 2; i <= n; i++) {
		while (j && s[i] != s[j + 1])
			j = nxt[j];
		if (s[i] == s[j + 1]) {
			++j;
		}
		nxt[i] = j;
	}

	n -= nxt[n];

	for (int l = 1; l <= n; l++)
		s[l + n] = s[l];
	int i = 1; j = 2;
	while (j <= n) {
		int k = 0;
		while (k < n && s[i + k] == s[j + k])
			++k;
		if (s[i + k] > s[j + k])
			i += k + 1;
		else
			j += k + 1;
		if (i == j)
			++j;
		if (i > j)
			swap(i, j);
	}

	for (int l = i; l <= i + n - 1; l++)
		printf("%c",s[l]);

	return;
}



int main()
{
	scanf("%s",s+1);
	getmin11(s);

	return 0;
}

 